The subject matter discussed herein relates generally to methods and systems of detecting leakage of sensitive information while also preserving privacy, and more particularly, to a protocol between an external host and an enterprise to detect large-scale data leakage in a manner that protects private information.